/**
 * 42. 接雨水
 * 
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 * 
 * 示例 1：见图T42
 * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出：6
 * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
 * 
 * 示例 2：
 * 输入：height = [4,2,0,3,2,5]
 * 输出：9
 * 
 * 提示：
 * n == height.length
 * 0 <= n <= 3 * 104
 * 0 <= height[i] <= 10^5
 * 
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/trapping-rain-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * 
 */

package zw;

public class T42 {
	public int trap(int[] height) {
		int front = 0;
		int result = 0;
		while(front < height.length) {
			boolean flag = false;
			int rightMax = front + 1; // 右边柱子中最高的
			for(int behind = front + 1; behind < height.length; behind++) {
				rightMax = height[behind] >= height[rightMax] ? behind : rightMax;
				if(height[behind] >= height[front]) { // 后面的柱子高于前面的柱子
					flag = true;
					result += calculate(front, behind, height);
					front = behind;
					break;
				}
			}
			if(!flag) {
				if(rightMax < height.length) {
					result += calculate(front, rightMax, height);
				}
				front = rightMax;
			}
		}
		return result;
    }
	
	private int calculate(int front, int behind, int[] height) {
		int shorter = height[front] > height[behind] ? height[behind] : height[front];
		int result = shorter * (behind - front - 1);
		for(int i = front+1; i < behind; i++) {
			result -= height[i];
		}
		return result;
	}
	
	// 动态规划（对于下标 ii，下雨后水能到达的最大高度等于下标 ii 两边的最大高度的最小值，
	// 下标 i 处能接的雨水量等于下标 i 处的水能到达的最大高度减去 height[i]。
	public int trap2(int[] height) {
		if(height.length == 0) {
            return 0;
        }
		int result = 0;
		// leftMax标记坐标i处及其左边的最高柱子所在位置
		int[] leftMax = new int[height.length];
		leftMax[0] = height[0];
		for(int i = 1; i < height.length; i++) {
			leftMax[i] = height[i] >= leftMax[i-1] ? height[i] : leftMax[i-1];
		}
		
		// rightMax标记坐标i处及其右边的最高柱子所在位置
		int[] rightMax = new int[height.length];
		rightMax[height.length-1] = height[height.length-1];
		for(int i = height.length-2; i >= 0 ; i--) {
			rightMax[i] = height[i] >= rightMax[i+1] ? height[i] : rightMax[i+1];
		}
		
		for(int i = 1; i < height.length-1; i++) {
			int shorter = leftMax[i] < rightMax[i] ? leftMax[i] : rightMax[i];
			if(shorter > height[i]) {
				result += shorter - height[i];
			}
		}
		return result;
	}
	
	// 双指针  动态规划优化 只占用O(1)的空间
	public int trap3(int[] height) {
		if(height.length == 0) {
			return 0;
		}
		int result = 0;
		int leftMax = height[0];
		int rightMax = height[height.length-1];
		int left = 0;
		int right = height.length-1;
		while(left < right) {
			rightMax = rightMax > height[right] ? rightMax : height[right];
			leftMax = leftMax > height[left] ? leftMax : height[left];
			if(leftMax > rightMax) {
				result += rightMax - height[right];
				right--;
			} else {
				result += leftMax - height[left];
				left++;
			}
		}
		return result;
	}
	
	public static void main(String[] args) {
		T42 t42 = new T42();
		System.out.print(t42.trap3(new int[] {0,1,0,2,1,0,1,3,2,1,2,1}));
	}
}
